package 二叉树高频题目_下_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 普通二叉树上寻找两个节点的最近公共祖先
// 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
public class Code01_LowestCommonAncestor {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            // 遇到空，或者p，或者q，直接返回
            return root;
        }
        // 左树搜p和q：// 遇到空，或者p，或者q，直接返回
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 右树搜p和q：// 遇到空，或者p，或者q，直接返回
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null){
            // 左树也搜到，右树也搜到，返回root
            return root;
        }
        if(left == null && right == null){
            // 都没搜到返回空
            return null;
        }
        // l和r一个为空，一个不为空
        // 返回不空的那个
        return left != null ? left : right;
    }

}
